The present invention relates generally to the field of handling processor deadlocks, and more particularly to recording deadlock information in a “lock dependency graph.”
In computer science, a deadlock is a situation where multiple actions, processes and/or resources are waiting for the other to finish, in a circular fashion. For example: (i) in a two-way deadlock, process A waits on process B, and process B waits on process A; (ii) in a three-way deadlock, process A waits on process B, process B waits on process C, and process C waits on process A; and (iii) and so on. In the language of the art, a “resource” typically does not wait for another resource. Rather, it is almost always the case that “processes” wait for resources, because processes are the active entities in the system. A typical 2-process deadlock can be described as a situation which occurs when a process A holding a resource A enters a waiting state because a resource B that it is requesting, is held by a different process B, and this process B in turn is waiting on the resource A which is held by process A. In other words, processes A and B end up waiting forever on each other to release their respective resources, and hence both fail to make any forward progress. The system is then said to be in a deadlock. This scenario can also be extended to describe a multi-process deadlock, where a group of more than 2 processes end up waiting on processes within that group in a circular fashion, such that each process waits indefinitely on another process and hence cannot achieve any forward progress.
A system is in a state of deadlock when the “Wait-for Graph” (as in who waits for whom) for the entities in question has a cycle in the graph (that is, there is a circular dependency between the entities, for example: A waits for B and B waits for A, and no action/process/resource gives up on waiting).
One known technique that helps with detecting, predicting and/or handling of processor deadlocks is the use of a “lock dependency graph.” Conventionally, an up-to-date lock dependency graph can let the system know that a deadlock is about to happen.
“Lock dependency graph” is defined, for purposes of this document, as a set of information about “locks” that currently exist, or are imminently expected to come to exist, in a computer system; a “lock dependency graph” may additionally maintain detailed information about nesting of locks and/or information regarding how and when locks are acquired and/or are to be released. Conventionally, the “locks” recognized by the “lock dependency graph” are limited to the following types of “locking primitives”: (i) acquiring or releasing a spin-lock (single-holder non-sleepable lock); (ii) acquiring a spin-lock accompanied by disabling the interrupts, or releasing a spin-lock accompanied by enabling the interrupts; (iii) acquiring or releasing a reader-writer spin-lock (also known, more simply, as “reader-writer lock”) for read; (iv) acquiring or releasing a reader-writer spin-lock for write; (v) acquiring a reader-writer spin-lock for read, accompanied by disabling the interrupts or releasing a reader-writer spin-lock for read, accompanied by enabling the interrupts; (vi) acquiring a reader-writer spin-lock for write, accompanied by disabling the interrupts or releasing a reader-writer spin-lock for write, accompanied by enabling the interrupts; (vii) acquiring or releasing a mutex-lock (single-holder sleepable lock); (viii) acquiring or releasing a semaphore (sleepable lock with user-defined degree of concurrent access to the protected resource or critical section); (ix) acquiring or releasing a reader-writer semaphore for read; and (x) acquiring or releasing a reader-writer semaphore for write. Herein, a lock acquired under one of the foregoing types of conventionally recognized locking primitives will be referred to as a “conventional lock.”